home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / us20src.zip / BIC.C < prev    next >
C/C++ Source or Header  |  1992-06-27  |  11KB  |  578 lines
  1. /*    BIC:    Bickel's Algorithm test program
  2.         Spell Checker and Corrector
  3.  
  4.         (C)opyright May 1990, 1991 by Daniel Lawrence
  5.         All Rights Reserved
  6.  
  7.     Revision History:
  8.     29-mar-91    Trying some filters to improve this
  9. */
  10.  
  11. #define    maindef    1
  12.  
  13. #include    <stdio.h>
  14. #include    <ctype.h>
  15. #include    "dopt.h"
  16. #include    "dstruct.h"
  17. #include    "ddef.h"
  18.  
  19.  
  20. #define    MWSIZE    40        /* maximum # chars in a word */
  21.  
  22. /*    letter weighing table    */
  23.  
  24. char lweight[26] = {
  25.     /* a */    3,
  26.     /* b */    6,
  27.     /* c */    5,
  28.     /* d */    4,
  29.     /* e */    3,
  30.     /* f */    5,
  31.     /* g */    5,
  32.     /* h */    4,
  33.     /* i */    3,
  34.     /* j */    8,
  35.     /* k */    7,
  36.     /* l */    4,
  37.     /* m */    5,
  38.     /* n */    3,
  39.     /* o */    3,
  40.     /* p */    5,
  41.     /* q */    7,
  42.     /* r */    4,
  43.     /* s */    3,
  44.     /* t */    3,
  45.     /* u */    4,
  46.     /* v */    6,
  47.     /* w */    5,
  48.     /* x */    8,
  49.     /* y */    8,
  50.     /* z */    9
  51. };
  52.  
  53. /*    some limits    */
  54. #define    MAXMATCHES    50
  55.  
  56. /*    local prototypes    */
  57.  
  58. #if    TURBO
  59. char *cleanword(char *word);
  60. char *sortword(char *word);
  61. char *intersect(char *word1, char *word2);
  62. int weight(char *cletters);
  63. int mismatch(char *, char *);
  64. #else
  65. char *cleanword();
  66. char *sortword();
  67. char *intersect();
  68. int weight();
  69. int mismatch();
  70. #endif
  71.  
  72. /*    GLOBALS for BIC    */
  73.  
  74. char testwrd[MWSIZE];        /* word to test against dictionary */
  75. char sortwrd[MWSIZE];        /* sorted letters of testwrd */
  76. char dictwrd[MWSIZE];        /* dictionary word to compare */
  77. int likeness;            /* likeness score of current word */
  78. int threshold;            /* threshold to display likeness */
  79. int max_matches;        /* maximum number of matches */
  80. char matches[MAXMATCHES][128];    /* list of current matches */
  81. int match_scores[MAXMATCHES];    /* difference scores for these */
  82. int swterse = FALSE;        /* called from EMACS? */
  83. int swverbose = FALSE;        /* display extra info? */
  84. int exact_match = FALSE;    /* is this word in the dictionary? */
  85.  
  86. main(argc, argv)
  87.  
  88. int argc;    /* command line argument count */
  89. char **argv;    /*              argument vector */
  90.  
  91. {
  92.     register int dif_value;    /* difference value of current word */
  93.     register char *sortptr;    /* ptr to the sorted cleaned dictionary word */
  94.     register char first_char; /* first character in word to test */
  95.  
  96.     max_matches = 12;    /* default list length! */
  97.  
  98.     if (argc < 2) {
  99.         usage();
  100.         exit(EXBADOPT);
  101.     }
  102.  
  103.     /* deal with the command options */
  104.     while (argc > 1) {
  105.  
  106.         /* grab the next option */
  107.         --argc;
  108.         argv++;
  109.         strcpy(testwrd, argv[0]);
  110.  
  111.         if (*testwrd == '-') {
  112.  
  113.             switch (testwrd[1]) {
  114.  
  115.                 case 'm':
  116.                     --argc;
  117.                     argv++;
  118.                     max_matches = atoi(argv[0]);
  119.                     break;
  120.  
  121.                 case 't':
  122.                     swterse = TRUE;
  123.                     break;
  124.  
  125.                 case 'v':
  126.                     swverbose = TRUE;
  127.                     break;
  128.  
  129.                 default:
  130.                     usage();
  131.                     exit(EXBADOPT);
  132.             }
  133.         }
  134.  
  135.     }
  136.  
  137.     /* announce us */
  138.     if (swterse == FALSE)
  139.         printf("BIC %s    Bickel's Test Algorithm\n", VERSION);
  140.  
  141.     /* initialize the lcase array */
  142.     init_lcase();
  143.  
  144.     /* grab the test word */
  145.     strcpy(sortwrd, sortword(cleanword(testwrd)));
  146.     threshold = weight(intersect(sortwrd, sortwrd)) - 4;
  147.     if (swverbose)
  148.         printf("threshold = %u\n", threshold);
  149.  
  150.     /* initailize the list of matches */
  151.     init_match();
  152.  
  153.     /* open the main dictionary */
  154.     if (mopen() == FALSE)
  155.         exit(EXMDICT);
  156.  
  157.     first_char = lcase[*testwrd];
  158.     skipdict(first_char);
  159.     strcpy(dictwrd, nxtmword());
  160.  
  161.     /* scan the dictionary */
  162.     while (lcase[*dictwrd] == first_char) {
  163.  
  164.         /* dump them if off by more than 3 chars! */
  165.         if (abs(strlen(dictwrd) - strlen(testwrd)) < 4) {
  166.  
  167.             /* clean and sort the word */
  168.             sortptr = sortword(cleanword(dictwrd));
  169.  
  170.             /* calculate the likeness score */
  171.             likeness = weight(intersect(sortwrd, sortptr));
  172.  
  173.             /* tell us about it */
  174.             if (likeness > threshold) {
  175.  
  176.                 /* are these nearly alike? */
  177.                 if ((dif_value = mismatch(sortwrd, sortptr)) < 20) {
  178.                     add_match(dictwrd, dif_value);
  179.  
  180.                     /* is this the word? */
  181.                     if (strcmp(testwrd, dictwrd) == 0) {
  182.                         exact_match = TRUE;
  183.                         if (swterse) {
  184.                             printf("EXACT MATCH\n");
  185.                             mclose();
  186.                             exit(EXGOOD);
  187.                         }
  188.                     }
  189.     
  190.                 }
  191.             }
  192.         }
  193.  
  194.         /* get a dictionary word */
  195. nextword:    strcpy(dictwrd, nxtmword());
  196.  
  197.         /* at the end... skip out */
  198.         if (strcmp(dictwrd, hivalue) == 0)
  199.             break;
  200.     }
  201.  
  202.     /* close the main dictionary */
  203.     mclose();
  204.  
  205.     /* show us the results */
  206.     show_match();
  207.  
  208.     /* error code of EXMISS if word is not in dictionary */
  209.     if (exact_match) {
  210.         exit(EXGOOD);
  211.     } else {
  212.         exit(EXMISS);
  213.     }
  214. }
  215.  
  216. usage()        /* print the command line usage */
  217.  
  218. {
  219.     printf("BIC:    Bickel's Algorithm Test Program\n");
  220.     printf("    for MicroSPELL %s\n",VERSION);
  221.     puts("\nUsage\n");
  222.     puts("    BIC {-t|-v} {-m <n>} <test word>\n");
  223.     puts("        -m <n>    return top <n> suggestions / default = 12");
  224.     puts("        -t    terse mode");
  225.     puts("        -v    verbose mode");
  226. }
  227.  
  228.  
  229. #if    RAMSIZE & LATTICE & MSDOS
  230. /*    These routines will allow me to track memory usage by placing
  231.     a layer on top of the standard system malloc() and free() calls.
  232.     with this code defined, the number of allocated bytes is displayed
  233.     in the upper right corner of the screen
  234. */
  235.  
  236. #undef    malloc
  237. #undef    free
  238.  
  239. char *allocate(nbytes)    /* allocate nbytes and track */
  240.  
  241. unsigned nbytes;    /* # of bytes to allocate */
  242.  
  243. {
  244.     char *mp;    /* ptr returned from malloc */
  245.     char *malloc();
  246.  
  247.     mp = malloc(nbytes);
  248.     if (mp) {
  249.         envram += nbytes;
  250. #if    RAMSHOW
  251.         dspram();
  252. #endif
  253.     }
  254.  
  255.     return(mp);
  256. }
  257.  
  258. release(mp)    /* release malloced memory and track */
  259.  
  260. char *mp;    /* chunk of RAM to release */
  261.  
  262. {
  263.     unsigned *lp;    /* ptr to the long containing the block size */
  264.  
  265.     if (mp) {
  266.         lp = ((unsigned *)mp) - 1;
  267.  
  268.         /* update amount of ram currently malloced */
  269.         envram -= (long)*lp - 2;
  270.         free(mp);
  271. #if    RAMSHOW
  272.         dspram();
  273. #endif
  274.     }
  275. }
  276.  
  277. #if    RAMSHOW
  278. dspram()    /* display the amount of RAM currently malloced */
  279.  
  280. {
  281.     char mbuf[20];
  282.     char *sp;
  283.  
  284. /*    TTmove(term.t_nrow - 1, 70);*/
  285.     sprintf(mbuf, "[%lu]", envram);
  286.     sp = &mbuf[0];
  287.     puts(sp);
  288. }
  289. #endif
  290. #endif
  291.  
  292. #if    AZTEC & MSDOS
  293. #undef    fgetc
  294. /*    a1getc:        Get an ascii char from the file input stream
  295.             but DO NOT strip the high bit
  296. */
  297.  
  298. int a1getc(fp)
  299.  
  300. FILE *fp;
  301.  
  302. {
  303.     int c;        /* translated character */
  304.  
  305.     c = getc(fp);    /* get the character */
  306.  
  307.     /* if its a <LF> char, throw it out  */
  308.     while (c == 10)
  309.         c = getc(fp);
  310.  
  311.     /* if its a <RETURN> char, change it to a LF */
  312.     if (c == '\r')
  313.         c = '\n';
  314.  
  315.     /* if its a ^Z, its an EOF */
  316.     if (c == 26)
  317.         c = EOF;
  318.  
  319.     return(c);
  320. }
  321. #endif
  322.  
  323. #if    CMS
  324. #undef    fopen
  325. /*    The IBM 30xx likes to tell us when file opens
  326.     fail...it's too chatty....I like to handle these myself    */
  327.  
  328. FILE *cmsopen(file, mode)
  329.  
  330. char *file;    /* name of file to open */
  331. char *mode;    /* mode to open it in */
  332.  
  333. {
  334.     quiet(1);
  335.     return(fopen(file,mode));
  336. }
  337. #endif
  338.  
  339. /**********************************************************************/
  340.  
  341. /*    clean word:    dump all the non alpha chars, and make them
  342.             lowercase only
  343. */
  344.  
  345. char *cleanword(word)
  346.  
  347. char *word;    /* word to clean */
  348.  
  349. {
  350.     register char *sp;        /* ptr into return buffer */
  351.     static char rbuf[MWSIZE];    /* return buffer */
  352.  
  353.     /* scan through the word */
  354.     sp = rbuf;
  355.     while (*word) {
  356.         if (isalpha(*word)) {
  357.             if (islower(*word))
  358.                 *sp++ = *word;
  359.             else
  360.                 *sp++ = *word + 32;
  361.         }
  362.  
  363.         ++word;
  364.     }
  365.  
  366.     *sp = 0;
  367.     return(rbuf);
  368. }
  369.  
  370. /*    Sort word:  bubble sort the letters in a word....
  371.             average word size is 4.5 chars. Bubble sort
  372.             is most efficient at that size
  373. */
  374.  
  375. char *sortword(word)
  376.  
  377. char *word;    /* word to sort letters in */
  378.  
  379. {
  380.     register int i, j;        /* bubble sort indexes */
  381.     register int temp;        /* temp for swap */
  382.     register int swapflag;        /* did a swap occur? */
  383.     static char sword[MWSIZE];    /* return buffer */
  384.  
  385.     /* copy the word to the return buffer */
  386.     strcpy(sword, word);
  387.  
  388.     /* bubble sort it */
  389.     for (i = strlen(sword) - 1; i > 0; i--) {
  390.  
  391.         /* scan through the list once */
  392.         swapflag = FALSE;
  393.         for (j = 0; j < i; j++) {
  394.  
  395.             /* compare */
  396.             if (sword[j] > sword[j + 1]) {
  397.  
  398.                 temp = sword[j];
  399.                 sword[j] = sword[j + 1];
  400.                 sword[j + 1] = temp;
  401.                 swapflag = TRUE;
  402.             }
  403.         }
  404.  
  405.         /* if no movement occurred, we are done early */
  406.         if (swapflag == FALSE)
  407.             break;
  408.     }
  409.  
  410.     return(sword);
  411. }
  412.  
  413. /*    intersect:    find all letters occuring in 2 words    */
  414.  
  415. char *intersect(word1, word2)
  416.  
  417. char *word1;    /* first word to intersect with */
  418. char *word2;    /*     second word */
  419.  
  420. {
  421.     register char *iptr;        /* ptr into return buffer */
  422.     static char rbuf[MWSIZE];    /* return buffer */
  423.  
  424.     /* scan through both words */
  425.     iptr = rbuf;
  426.     while (*word1 && *word2) {
  427.  
  428.         /* if they are the same, record it */
  429.         if (*word1 == *word2) {
  430.             *iptr = *word1++;
  431.             ++word2;
  432.  
  433.             /* skip duplicates */
  434.             while (*word1 == *iptr)
  435.                 ++word1;
  436.             while (*word2 == *iptr)
  437.                 ++word2;
  438.  
  439.             ++iptr;
  440.  
  441.             continue;
  442.         }
  443.  
  444.         /* advance the appropriate word */
  445.         if (*word1 < *word2)
  446.             ++word1;
  447.         else
  448.             ++word2;
  449.     }
  450.  
  451.     /* terminate and return the intersection */
  452.     *iptr = 0;
  453.     return(rbuf);
  454. }
  455.  
  456. /*    weight:    using the common letters between two words, apply
  457.         bickels weighing function to produce a sameness score
  458. */
  459.  
  460. int weight(cletters)
  461.  
  462. char *cletters;        /* common letters between two words */
  463.  
  464. {
  465.     int result;    /* resulting weighing factor */
  466.  
  467.     /* scan the letters, add up the result */
  468.     result = 0;
  469.     while (*cletters)
  470.         result += lweight[*cletters++ - 'a'];
  471.  
  472.     return(result);
  473. }
  474.  
  475. /* How many characters are different between these words? */
  476.  
  477. int mismatch(word1, word2)
  478.  
  479. char *word1;    /* first word to compare */
  480. char *word2;    /* second word to compare */
  481.  
  482. {
  483.     int count;    /* count of mismatched characters */
  484.  
  485.     count = 0;
  486.     while (*word1) {
  487.  
  488.         /* at the end of word2? */
  489.         if (*word2 == 0) {
  490.             count += lweight[*word1-'a'];
  491.             ++word1;
  492.         } else {
  493.  
  494.             /* a match, advance */
  495.             if (*word1 == *word2) {
  496.                 ++word1;
  497.                 ++word2;
  498.             } else {
  499.                 if (*word1 < *word2) {
  500.                     count += lweight[*word1-'a'];
  501.                     ++word1;
  502.                 } else {
  503.                     count += lweight[*word2-'a'];
  504.                     ++word2;
  505.                 }
  506.             }
  507.         }
  508.     }
  509.  
  510.     /* past the rest */
  511.     while (*word2) {
  512.         ++count;
  513.         count += lweight[*word2-'a'];
  514.         ++word2;
  515.     }
  516.  
  517.     return(count);
  518. }
  519.  
  520. init_match()
  521.  
  522. {
  523.     register int index;
  524.  
  525.     for (index = 0; index < max_matches; index++) {
  526.         matches[index][0] = 0;
  527.         match_scores[index] = 1000;
  528.     }
  529. }
  530.  
  531. add_match(word, score)
  532.  
  533. char *word;    /* word to add to match list */
  534. int score;    /* score of that word */
  535.  
  536. {
  537.     register int index;    /* ptr into match list */
  538.     register int rest;    /* ptr into rest of list to move */
  539.  
  540.     for (index = 0; index < max_matches; index++) {
  541.         if (match_scores[index] > score) {
  542.             for (rest = max_matches; rest > index; --rest) {
  543.                 match_scores[rest] = match_scores[rest-1];
  544.                 strcpy(matches[rest], matches[rest-1]);
  545.             }
  546.             match_scores[index] = score;
  547.             strcpy(matches[index], word);
  548.             return;
  549.         }
  550.     }
  551. }
  552.  
  553. show_match()
  554.  
  555. {
  556.     register int index;
  557.     register int split;
  558.  
  559.     if (swterse == FALSE) {
  560.         for (index = 0; index < max_matches; index++) {
  561.             if (match_scores[index] > 999)
  562.                 return;
  563.             if (swverbose)
  564.                 printf("[%u] %s\n", match_scores[index], matches[index]);
  565.             else
  566.                 printf("%s\n", matches[index]);
  567.         }
  568.     } else {
  569.         split = (max_matches + 2) / 3;
  570.         for (index = 0; index < split; index++) {
  571.             printf("%20s %20s %20s \n",
  572.                 matches[index],
  573.                 matches[index + split],
  574.                 matches[index + split * 2]);
  575.         }
  576.     }
  577. }    
  578.